1. Field of the Invention
The current invention relates to cryptographic-processing functions, and in particular, to encryption and decryption using a processor.
2. Description of the Related Art
Encryption and decryption are cryptographic processes that convert plaintext into ciphertext and vice-versa, respectively. Plaintext refers to text-based data (i.e., a sequence of bit strings) that is typically readily readable by and comprehensible to a human. Note that, more generally, plaintext refers to the input to an encryption algorithm, and the plaintext may well be gibberish. Data encryption is a process used to convert plaintext into ciphertext, where ciphertext typically appears to be gibberish not readily readable by or comprehensible to a human. Note that, more generally, ciphertext refers to the output of an encryption algorithm, and the ciphertext might happen to resemble recognizable text. A typical flow of information in cryptography involves inputting original plaintext into an encryption algorithm that outputs ciphertext, transmitting the ciphertext, and then inputting the ciphertext into a complementary decryption algorithm that outputs the original plaintext.
One way to encrypt plaintext involves using a key. The resulting ciphertext is then decrypted using the appropriate corresponding key. A cryptographic system that uses the same key for both encryption and decryption is known as a symmetric cryptographic system. A collection of functions and their inverses that use keys and map strings of a fixed length to strings of the same length is known as a block cipher. One popular symmetric block cipher is the Advanced Encryption Standard (AES), described in Federal Information Processing Standards (FIPS) Publication 197, incorporated herein by reference in its entirety. Older FIPS-approved symmetric block ciphers include the Data Encryption Standard (DES) and triple-DES.
Symmetric block ciphers are used in multiple endeavors and for multiple purposes. One common use for symmetric block ciphers is for the cryptographic protection of transmitted data. AES may be used to encrypt and decrypt secure real-time protocol (SRTP) packets. SRTP is a secure version of RTP, where RTP is a protocol for delivering media content over a packet-switched network, such as the Internet. SRTP provides security, integrity, and authentication for RTP packets.
The AES algorithm, as currently defined, processes data in block sizes of 128 bits. Data block size is represented by Nb, where Nb is the number of 32-bit words in a block. Thus, for 128-bit blocks, Nb=4. The length of the cipher key used is represented by Nk, where Nk is the number of 32-bit words in the cipher key. The AES standard, as currently defined, allows use of cipher keys with lengths of 128 bits (wherein Nk=4), 192 bits (Nk=6), or 256 bits (Nk=8). A particular implementation of the AES standard should support at least one of the standard cipher-key lengths. A block of input data is transformed over a series of rounds, where the number of rounds, represented by Nr, is dependent on the length of the cipher key. There are 10 rounds when using 128-bit keys, 12 when using 192-bit keys, and 14 when using 256-bit keys. The AES standard recognizes that, in the future, the specific values for key length, block size, and number of rounds are subject to change.
The working data block, or intermediate cipher result, of AES encryption and decryption is known as the State, and can be represented as a rectangular array of bytes having four rows and four columns of 8-bit bytes (for a total of 128 bits). The bytes can be viewed as finite-field elements. They can be added and multiplied, but those operations are different from those used for numbers. For example, both addition and its inverse are implemented by performing an exclusive-OR (XOR) operation, while multiplication involves modulo reduction. Unless otherwise noted, references herein to addition mean the performance of an XOR operation. Encryption and decryption start with the copying of an input block of data into the State array, where the bytes of the State will be transformed over the requisite number of rounds, and then the State's final value will be provided as the corresponding output block. It should be noted that, depending on the particular AES mode of operation used, (1) the input data block may consist of data other than the corresponding plaintext or ciphertext block and (2) the output block may undergo additional transformations before resulting in the corresponding ciphertext or plaintext block.
FIG. 1 illustrates the transformation of input block 101 via State 102 into output block 103. 128-bit input block 101 comprises sixteen bytes, in0, . . . in15, arranged into an array of four rows and four columns. State 102, also comprising four rows and four columns of bytes, s0,0, . . . s3,3, is initialized to equal input block 101, where si,j=in[i+4j], with i and j representing row and column, respectively. Thus, the bytes the input block sequentially fill up the columns of State 102. State 102 is then modified over a number of rounds, after which State 102 is output to output block 103, which comprises sixteen bytes, out0, . . . out15, where out[i+4j]=si,j. Thus, output block 103 equals a sequential emptying of the columns of State 102.
The AES algorithm takes the cipher key, and performs a key expansion routine to generate a key schedule with a total of Nb(Nr+1) 32-bit (or 4-byte) words, which are used for both encryption and decryption. Each round of encryption or decryption uses a different set of Nb words from the key schedule. The first Nk words, equivalent to one cipher key length, of the expanded key schedule are filled with the cipher key. Every subsequent word of the key schedule is based on one or more of the previous words of the key schedule and zero or more constants.
For both its encryption and decryption, the AES algorithm uses a round function that is composed of four different byte-oriented transformations: (1) byte substitution using a substitution table (S-box), (2) shifting rows of the State array by different offsets, (3) mixing the data within each column of the State array, and (4) adding a round key to the State. Encryption starts with an initial stage in which an initial round key is added to the State. This initial stage is sometimes referred to as round zero. The initial stage is then followed by Nr rounds of transformations. The first Nr−1 rounds include the above four transformations, represented as SubBytes( ), ShiftRows( ), MixColumns( ), and AddRoundKey( ), respectively. Note that the final round of block encryption, i.e., round Nr, does not include the MixColumns( ) transformation. Also note that, although some descriptions of the AES standard state that the above-described transformations are not performed in the preliminary round (i.e., round zero), the addition of the round key in round zero is equivalent to performing the AddRoundKey( ) transformation.
FIG. 2 shows S-box 201 used for the SubBytes( ) transformation. Row {x} and column {y} of S-box 201 represent input 8-bit hexadecimal number {xy}, where the byte at the intersection of row {x} and column {y} represents the substitution output for {xy}. Thus, for example, an input of {a2} would result in an output of {3a}, which is the number at the intersection of row {a} and column {2}. As can be seen, SubBytes( ) substitutes one byte for another.
FIG. 3 shows the ShiftRows( ) transformation of State 301 into State 302. The ShiftRows( ) transformation performs a cyclic shift of row k by k positions to the left, where k=0 to 3. Thus, the first row (i.e., k=0) is not shifted, the second row is cyclically shifted one byte to the left, the third row is cyclically shifted two bytes to the left, and the fourth row is cyclically shifted three bytes to the left.
Next, the MixColumns( ) transformation operates on each of the four columns of the State in turn. The MixColumns( ) transformation involves multiplying modulo x4+1 each column, s(x), treated as a four-term polynomial over GF(28), with the fixed polynomial a(x)={03}x3+{01}x2+{01}x+{02}. The multiplication of column i can also be represented as a vector product of the old column s(x) with matrix a(x) representing the fixed polynomial, resulting in new columns sn(x), i.e., sn(x)=a(x)  s(x), where  represents multiplication modulo x4+1.
FIG. 4 shows the MixColumns( ) transformation for column j as the product of column j, shown as input vector 401, with matrix 402, representing the fixed polynomial, resulting in new column j, shown as output vector 403. The four elements of input vector 401 are s0,j, . . . , s3,j and the corresponding four elements of output vector 403 are sn0,j, . . . sn3,j. The elements of the resultant column product can be represented by the series of equations below, where ⊕ represents the exclusive-OR (XOR) operation and · represents finite-field polynomial multiplication in GF(28) modulo x8+x4+x3+x+1:sn0,j=({02}·s0,j)⊕({03}·s1,j)⊕s2,j⊕s3,j  (1.1)sn1,j=s0,j⊕({02}·s1,j)⊕({03}·s2,j)⊕s3,j  (1.2)sn2,j=s0,j⊕s1,j⊕({02}·s2,j)⊕({03}·s3,j)  (1.3)sn3,j=({03}·s0,j)⊕s1,j⊕s2,j⊕({02}·s3,j)  (1.4)
Following the MixColumns( ) transformation of all four columns, an AddRoundKey( ) transformation is performed where a 128-bit (or 16-byte) round key, from the expanded key schedule, is added (using a XOR operation) to the State column by column. The AddRoundKey( ) transformation can be represented by Equation (2) below, where sni,j represents elements of the transformed State, si, j represents elements of the pre-transformation State, wx represents a 4-byte segment of the expanded key schedule starting at byte x, and r represents the round number, where 0≦r≦Nr.[sn0,j,sn1,j,sn2,j,sn3,j]=[s0,j,s1,j,s2,j,s3,j]⊕[wr*Nb+j]  (2)After the final round, the State, containing encrypted data (i.e., ciphertext), is copied to output 103 of FIG. 1.
Straightforward AES decryption uses the inverse transformations of the encryption transformations. The decryption algorithm involves the following sequence of transformations: (1) InvShiftRows( ), (2) InvSubBytes( ), (3) AddRoundKey( ) (since XOR is its own inverse), and (4) InvMixColumns( ). Like encryption, decryption proceeds over an initial stage followed by Nr rounds using the same Nr+1 round keys used for encryption; however, the round keys are used in reverse order, starting with the final round key of the key schedule, stepping backwards through the expanded key schedule, and ending with the initial round key. The expanded key schedule is created in the same way as in the encryption process. Decryption starts with the copying of a block of encrypted data (i.e., ciphertext) to the State and the addition of the final round key of the key schedule to the State. This is followed by Nr−1 identical rounds of transformation, which include the above four inverse transformations, and wherein the AddRoundKey( ) transformation steps backwards through the key schedule. The final round (round Nr) does not include the InvMixColumns( ) transformation.
The AES standard also provides an equivalent decryption process that allows a reordering of the inverse procedures based on commutative and distributive properties of combinations of the procedures, and which is particularly beneficial for systems that perform both encryption and decryption. The equivalent decryption process requires the transformation of the round keys for rounds 1 to Nr−1 using an InvMixColumns( ) procedure, which can be accomplished by using the expanded key schedule and transforming the appropriate round keys therein. The equivalent decryption process starts with the addition of the final round key, i.e., the last Nb words of the key expansion schedule, followed by Nr−1 identical rounds of InvSubBytes( ), InvShiftRows( ), InvMixColumns( ), and AddRoundKey( ) transformations, respectively, stepping backwards through the key expansion schedule. The final round does not include the InvMixColumns( ) transformation for the State. After the final round, the content of the State is copied to the output.
It should be noted that several AES modes of operations such as, for example, cipher feedback mode (CFM) and output feedback mode (OFM), described in NIST Special Publication 800-38A, incorporated herein by reference in its entirety, both encryption and decryption use only the forward cipher function. In other words, (1) both encryption and decryption processing utilize the ShiftRows( ), SubBytes( ), MixColumns( ), and AddRoundKey( ) transformations and (2) neither needs to utilize the InvSubBytes( ), InvShiftRows( ), and InvMixColumns transformations.
Modifications of the methodologies described in the AES standard may provide for more-efficient encryption and decryption algorithms. In addition, adjusting the methodologies to take advantage of particular processor architectures may also provide for more-efficient encryption and decryption.